11504 - Dominos/11504.2.cpp

   1 /*
   2   Problem: 11504 - Dominos
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Accepted
   7  */
   8
   9 using namespace std;
  10 #include <iostream>
  11 #include <deque>
  12 #include <vector>
  13 #include <cassert>
  14 #include <set>
  15
  16 const int N = 100005;
  17
  18 vector<int> g[N], gt[N];
  19 set<int> gc[N];
  20 int visited[N], scc[N], color[N];
  21
  22 void dfs(int u, int mark, deque<int> *in_order, int visited[], vector<int> g[]){
  23   visited[u] = mark;
  24
  25   vector<int> &out = g[u];
  26   for (int k=0, m=out.size(); k<m; ++k){
  27     int v = out[k];
  28     if (!visited[v]) dfs(v, mark, in_order, visited, g);
  29   }
  30   if (in_order) in_order->push_front(u);
  31 }
  32
  33 enum { standing, tiled, handed };
  34 void shoot(int u, int root, set<int> g[]){
  35   if (u == root) color[u] = handed;
  36   else color[u] = tiled;
  37
  38   set<int> &out = g[u];
  39   for (set<int>::iterator k=out.begin(); k!=out.end(); ++k){
  40     if (color[*k] == handed && *k != root) color[*k] = tiled;
  41     else if (color[*k] == standing) shoot(*k, root, g);
  42   }
  43 }
  44
  45
  46 int main(){
  47   int t;
  48   for(cin >> t; t--;){
  49     int n, m; cin >> n >> m;
  50
  51     for (int i=0; i<=n; ++i) g[i].clear(), gt[i].clear(), gc[i].clear(), visited[i] = scc[i] = color[i] = 0;
  52
  53     for (int u, v, i=0; i<m && cin >> u >> v; ++i) g[u].push_back(v), gt[v].push_back(u);
  54
  55     deque<int> in_order;
  56
  57     for (int i=1; i<=n; ++i)
  58       if (!visited[i])
  59         dfs(i, 1, &in_order, visited, g);
  60
  61
  62     int id = 1;
  63     for (deque<int>::iterator i=in_order.begin(); i!=in_order.end(); ++i)
  64       if (!scc[*i])
  65         dfs(*i, id++, NULL, scc, gt);
  66
  67
  68     /*
  69     for (int i=0; i<=n; ++i){
  70       printf("ssc[%d] = %d\n", i, scc[i]);
  71     }
  72     cout << endl;
  73     */
  74
  75     /*
  76       Build strongly connected components graph in gc.
  77      */
  78     for (int i=1; i<=n; ++i){
  79       vector<int> &out = g[i];
  80       for (int k=0, m=out.size(); k<m; ++k){
  81         gc[scc[i]].insert(scc[out[k]]);
  82       }
  83     }
  84
  85     for(int i=1; i<id; ++i){
  86       if (!color[i])
  87           shoot(i, i, gc);
  88     }
  89
  90     int ans = 0;
  91
  92     for (int i=1; i<id; ++i){
  93       ans += (color[i] == handed);
  94     }
  95
  96     cout << ans << endl;
  97   }
  98   return 0;
  99 }
 100
 101
 102 /*
 103   Explicación del algoritmo:
 104
 105   Lo primero es ver que cada componente fuertemente conexa del grafo puede
 106   tumbarse completamente usando solo una ficha. Entonces primero reducimos
 107   el grafo a un DAG donde cada nodo representa una componente fuertemente
 108   conexa del grafo original.
 109
 110   Para encontrar la respuesta utilizamos el siguiente algoritmo:
 111   Tumbamos cada ficha a mano y seguimos el efecto dominó. Si alcanzamos
 112   otra ficha que había sido tumbada a mano, entonces esta segunda no necesita
 113   ser tumbada a mano.
 114  */